ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Locally decodable code</title>

</head>

Locally decodable code

</h1>

</header>

A locally decodable code (LDC) is an <a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">error-correcting code</a> that allows a single bit of the original message to be decoded <a href="With_high_probability" title="With high probability">with high probability</a> by only examining (or querying) a small number of bits of a possibly corrupted <a href="Code_word_(communication)" title="Code word (communication)">codeword</a>.<a href="#cite_note-LDCSurvey-1">[1]</a><a href="#cite_note-PrivateLDC-2">[2]</a><a href="#cite_note-newLDCPIR-3">[3]</a>

This property could be useful, say, in a context where information is being transmitted over a noisy channel, and only a small subset of the data is required at a particular time and there is no need to decode the entire message at once. Locally decodable codes are not a subset of <a href="Locally_testable_code" title="Locally testable code">locally testable codes</a>, though there is some overlap between the two.<a href="#cite_note-LTCvsLDC-4">[4]</a>

Codewords are generated from the original message using an algorithm that introduces a certain amount of redundancy into the codeword; thus, the codeword is always longer than the original message. This redundancy is distributed across the codeword and allows the original message to be recovered with good probability even in the presence of errors. The more redundant the codeword, the more resilient it is against errors, and the fewer queries required to recover a bit of the original message.

<div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2></div>

More formally, a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (q,\delta ,\epsilon )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (q,\delta ,\epsilon )}</annotation>

</semantics>

</math><img src="./34a4ef76b4ea6950e34b1526072d7e4a998b28f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.94ex; height:2.843ex;" alt="{\displaystyle (q,\delta ,\epsilon )}" loading="lazy">-locally decodable code encodes an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-bit message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> to an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">-bit codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C(x)}</annotation>

</semantics>

</math><img src="./7f6b53682fddbe3028ffd75bd75771b86c6c7bd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.905ex; height:2.843ex;" alt="{\displaystyle C(x)}" loading="lazy"> such that any bit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> of the message can be recovered with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-\epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-\epsilon }</annotation>

</semantics>

</math><img src="./57f9b07affe80ff61cdc4f2e47977c8421a59c73.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.947ex; height:2.343ex;" alt="{\displaystyle 1-\epsilon }" loading="lazy"> by using a randomized decoding algorithm that queries only <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> bits of the codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C(x)}</annotation>

</semantics>

</math><img src="./7f6b53682fddbe3028ffd75bd75771b86c6c7bd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.905ex; height:2.843ex;" alt="{\displaystyle C(x)}" loading="lazy">, even if up to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta N}</annotation>

</semantics>

</math><img src="./5b86c9ae790068cf0d74998ab878914eeab62aa4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.112ex; height:2.343ex;" alt="{\displaystyle \delta N}" loading="lazy"> locations of the codeword have been corrupted.

Furthermore, a perfectly smooth local decoder is a decoder such that, in addition to always generating the correct output given access to an uncorrupted codeword, for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j\in [q]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j\in [q]}</annotation>

</semantics>

</math><img src="./c32170fb408b840ac9f142661674e4e4db5be795.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.027ex; width:6.189ex; height:2.843ex;" alt="{\displaystyle j\in [q]}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in [n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in [n]}</annotation>

</semantics>

</math><img src="./1b389a8f1ad8a43d2bcf5194acf34e934f806311.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.332ex; height:2.843ex;" alt="{\displaystyle i\in [n]}" loading="lazy"> the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j^{th}}</annotation>

</semantics>

</math><img src="./04bfd24f79d376ca8156511feb951588f358a928.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:2.758ex; height:3.009ex;" alt="{\displaystyle j^{th}}" loading="lazy"> query to recover the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i^{th}}</annotation>

</semantics>

</math><img src="./9c454bb35f050556d361ee85e06ca923b16a3bf4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.575ex; height:2.676ex;" alt="{\displaystyle i^{th}}" loading="lazy"> bit is uniform over <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [N]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [N]}</annotation>

</semantics>

</math><img src="./82c5c29e2a04165395b2e0896d9425fd0039fc8b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.357ex; height:2.843ex;" alt="{\displaystyle [N]}" loading="lazy">.<a href="#cite_note-AppCodingTheory-5">[5]</a>

(The notation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [y]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [y]}</annotation>

</semantics>

</math><img src="./f637a17dac262ee0fc8d58e31d08ca3ebe5a0fed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.449ex; height:2.843ex;" alt="{\displaystyle [y]}" loading="lazy"> denotes the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{1,\ldots ,y\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{1,\ldots ,y\}}</annotation>

</semantics>

</math><img src="./30355c150b7afa7c24b967e7e7919f2337d8b682.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.821ex; height:2.843ex;" alt="{\displaystyle \{1,\ldots ,y\}}" loading="lazy">). Informally, this means that the set of queries required to decode any given bit are uniformly distributed over the codeword.

Local list decoders are another interesting subset of local decoders. List decoding is useful when a codeword is corrupted in more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta /2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta /2}</annotation>

</semantics>

</math><img src="./d123312dff6f7c268bfadd93f6d1f7ef77c5513c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.374ex; height:2.843ex;" alt="{\displaystyle \delta /2}" loading="lazy"> places, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>

</semantics>

</math><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy"> is the minimum <a href="Hamming_distance" title="Hamming distance">Hamming distance</a> between two codewords. In this case, it is no longer possible to identify exactly which original message has been encoded, since there could be multiple codewords within <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>

</semantics>

</math><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy"> distance of the corrupted codeword. However, given a radius <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>

</semantics>

</math><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy">, it is possible to identify the set of messages that encode to codewords that are within <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>

</semantics>

</math><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy"> of the corrupted codeword. An upper bound on the size of the set of messages can be determined by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>

</semantics>

</math><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>

</semantics>

</math><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy">.<a href="#cite_note-6">[6]</a>

Locally decodable codes can also be concatenated, where a message is encoded first using one scheme, and the resulting codeword is encoded again using a different scheme. (Note that, in this context, <a href="Concatenation" title="Concatenation">concatenation</a> is the term used by scholars to refer to what is usually called <a href="Function_composition" title="Function composition">composition</a><a href="#cite_note-AppCodingTheory-5">[5]</a>). This might be useful if, for example, the first code has some desirable properties with respect to rate, but it has some undesirable property, such as producing a codeword over a non-binary alphabet. The second code can then transform the result of the first encoding over a non-binary alphabet to a binary alphabet. The final encoding is still locally decodable, and requires additional steps to decode both layers of encoding.<a href="#cite_note-7">[7]</a>

<div class="mw-heading mw-heading2"><h2 id="Length_of_codeword_and_query_complexity">Length of codeword and query complexity</h2></div>

The rate of a code refers to the ratio between its message length and codeword length: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {|x|}{|C(x)|}}}">

<mfrac>

<mrow>

</mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {|x|}{|C(x)|}}}</annotation>

</semantics>

</math><img src="./eed7b6614be2a2d15fbda22ab8d8fcc8c61e9f90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:7.035ex; height:6.509ex;" alt="{\displaystyle {\frac {|x|}{|C(x)|}}}" loading="lazy">, and the number of queries required to recover 1 bit of the message is called the query complexity of a code.

The rate of a code is inversely related to the query complexity, but the exact shape of this tradeoff is a major <a href="Open_problem" title="Open problem">open problem</a>.<a href="#cite_note-LDC1-8">[8]</a><a href="#cite_note-LDC2-9">[9]</a> It is known that there are no LDCs that query the codeword in only one position, and that the optimal codeword size for query complexity 2 is exponential in the size of the original message.<a href="#cite_note-LDC1-8">[8]</a> However, there are no known tight lower bounds for codes with query complexity greater than 2. Approaching the tradeoff from the side of codeword length, the only known codes with codeword length proportional to message length have query complexity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k^{\epsilon }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k^{\epsilon }}</annotation>

</semantics>

</math><img src="./705b5897e2587fb27c2843116d18f4d4fc5e9efc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.111ex; height:2.343ex;" alt="{\displaystyle k^{\epsilon }}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon >0}</annotation>

</semantics>

</math><img src="./568095ad3924314374a5ab68fae17343661f2a71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.205ex; height:2.176ex;" alt="{\displaystyle \epsilon >0}" loading="lazy"><a href="#cite_note-LDC1-8">[8]</a> There are also codes in between, that have codewords polynomial in the size of the original message and polylogarithmic query complexity.<a href="#cite_note-LDC1-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Locally decodable codes have applications to data transmission and storage, complexity theory, data structures, derandomization, theory of fault tolerant computation, and private information retrieval schemes.<a href="#cite_note-LDC2-9">[9]</a>

<div class="mw-heading mw-heading3"><h3 id="Data_transmission_and_storage">Data transmission and storage</h3></div>

Locally decodable codes are especially useful for data transmission over noisy channels. The <a href="Hadamard_code" title="Hadamard code">Hadamard code</a> (a special case of Reed Muller codes) was used in 1971 by <a href="Mariner_9" title="Mariner 9">Mariner 9</a> to transmit pictures of Mars back to Earth. It was chosen over a 5-repeat code (where each bit is repeated 5 times) because, for roughly the same number of bits transmitted per pixel, it had a higher capacity for error correction. (The Hadamard code falls under the general umbrella of <a href="Forward_error_correction" class="mw-redirect" title="Forward error correction">forward error correction</a>, and just happens to be locally decodable; the actual algorithm used to decode the transmission from Mars was a generic error-correction scheme.)<a href="#cite_note-10">[10]</a>

LDCs are also useful for data storage, where the medium may become partially corrupted over time, or the reading device is subject to errors. In both cases, an LDC will allow for the recovery of information despite errors, provided that there are relatively few. In addition, LDCs do not require that the entire original message be decoded; a user can decode a specific portion of the original message without needing to decode the entire thing.<a href="#cite_note-PIR-11">[11]</a>

<div class="mw-heading mw-heading3"><h3 id="Complexity_theory">Complexity theory</h3></div>

One of the applications of locally decodable codes in <a href="Computational_complexity_theory" title="Computational complexity theory">complexity theory</a> is hardness amplification. Using LDCs with polynomial codeword length and polylogarithmic query complexity, one can take a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L:\{0,1\}^{n}\rightarrow \{0,1\}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L:\{0,1\}^{n}\rightarrow \{0,1\}}</annotation>

</semantics>

</math><img src="./7498c704c6c427b5319297dcd525db1545d841a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.72ex; height:2.843ex;" alt="{\displaystyle L:\{0,1\}^{n}\rightarrow \{0,1\}}" loading="lazy"> that is hard to solve on worst case inputs and design a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L':\{0,1\}^{N}\rightarrow \{0,1\}}">

<msup>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L':\{0,1\}^{N}\rightarrow \{0,1\}}</annotation>

</semantics>

</math><img src="./c29a2bf353e432162ce3d3ace849688f8ccb0e11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.878ex; height:3.176ex;" alt="{\displaystyle L':\{0,1\}^{N}\rightarrow \{0,1\}}" loading="lazy"> that is hard to compute on average case inputs.

Consider <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> limited to only length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> inputs. Then we can see <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> as a binary string of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{t}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{t}}</annotation>

</semantics>

</math><img src="./c76195d5fba95fbb5aa31bdbf5ad2c8f9ea1849a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.988ex; height:2.509ex;" alt="{\displaystyle 2^{t}}" loading="lazy">, where each bit is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x)}</annotation>

</semantics>

</math><img src="./88b78cb2b3a60d964f3016e94f0d7bd081ebd3be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.722ex; height:2.843ex;" alt="{\displaystyle L(x)}" loading="lazy"> for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \{0,1\}^{t}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \{0,1\}^{t}}</annotation>

</semantics>

</math><img src="./7dd0125966e6b55df90636d582a3b0942ed2732d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.68ex; height:3.009ex;" alt="{\displaystyle x\in \{0,1\}^{t}}" loading="lazy">. We can use a polynomial length locally decodable code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> with polylogarithmic query complexity that tolerates some constant fraction of errors to encode the string that represents <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> to create a new string of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{O(t)}=2^{t'}}">

<msup>

</mrow>

</msup>

<msup>

<msup>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{O(t)}=2^{t'}}</annotation>

</semantics>

</math><img src="./8980c7d98bc9a02ce577970333c56507beb47804.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.14ex; height:2.843ex;" alt="{\displaystyle 2^{O(t)}=2^{t'}}" loading="lazy">. We think of this new string as defining a new problem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L'}</annotation>

</semantics>

</math><img src="./7a5bf7164faabe6b737c3d5269366b5e17f2ac7c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.268ex; height:2.509ex;" alt="{\displaystyle L'}" loading="lazy"> on length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t'}</annotation>

</semantics>

</math><img src="./a69b623f18f6b111645f0ec200b3271729fa99af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.524ex; height:2.509ex;" alt="{\displaystyle t'}" loading="lazy"> inputs. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L'}</annotation>

</semantics>

</math><img src="./7a5bf7164faabe6b737c3d5269366b5e17f2ac7c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.268ex; height:2.509ex;" alt="{\displaystyle L'}" loading="lazy"> is easy to solve on average, that is, we can solve <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L'}</annotation>

</semantics>

</math><img src="./7a5bf7164faabe6b737c3d5269366b5e17f2ac7c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.268ex; height:2.509ex;" alt="{\displaystyle L'}" loading="lazy"> correctly on a large fraction <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-\epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-\epsilon }</annotation>

</semantics>

</math><img src="./57f9b07affe80ff61cdc4f2e47977c8421a59c73.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.947ex; height:2.343ex;" alt="{\displaystyle 1-\epsilon }" loading="lazy"> of inputs, then by the properties of the LDC used to encode it, we can use <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L'}</annotation>

</semantics>

</math><img src="./7a5bf7164faabe6b737c3d5269366b5e17f2ac7c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.268ex; height:2.509ex;" alt="{\displaystyle L'}" loading="lazy"> to probabilistically compute <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> on all inputs. Thus, a solution to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L'}</annotation>

</semantics>

</math><img src="./7a5bf7164faabe6b737c3d5269366b5e17f2ac7c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.268ex; height:2.509ex;" alt="{\displaystyle L'}" loading="lazy"> for most inputs would allow us to solve <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> on all inputs, contradicting our assumption that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> is hard on worst case inputs.<a href="#cite_note-AppCodingTheory-5">[5]</a><a href="#cite_note-LDC1-8">[8]</a><a href="#cite_note-12">[12]</a>

<div class="mw-heading mw-heading3"><h3 id="Private_information_retrieval_schemes">Private information retrieval schemes</h3></div>

A <a href="Private_information_retrieval" title="Private information retrieval">private information retrieval</a> scheme allows a user to retrieve an item from a server in possession of a database without revealing which item is retrieved. One common way of ensuring privacy is to have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> separate, non-communicating servers, each with a copy of the database. Given an appropriate scheme, the user can make queries to each server that individually do not reveal which bit the user is looking for, but which together provide enough information that the user can determine the particular bit of interest in the database.<a href="#cite_note-newLDCPIR-3">[3]</a><a href="#cite_note-PIR-11">[11]</a>

One can easily see that locally decodable codes have applications in this setting. A general procedure to produce a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-server private information scheme from a perfectly smooth <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-query locally decodable code is as follows:

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> be a perfectly smooth LDC that encodes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-bit messages to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">-bit codewords. As a preprocessing step, each of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> servers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1},\ldots ,S_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1},\ldots ,S_{k}}</annotation>

</semantics>

</math><img src="./305f10651b52c158bdc6915995037bdba50745fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.171ex; height:2.509ex;" alt="{\displaystyle S_{1},\ldots ,S_{k}}" loading="lazy"> encodes the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-bit database <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> with the code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">, so each server now stores the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">-bit codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C(x)}</annotation>

</semantics>

</math><img src="./7f6b53682fddbe3028ffd75bd75771b86c6c7bd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.905ex; height:2.843ex;" alt="{\displaystyle C(x)}" loading="lazy">. A user interested in obtaining the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i^{th}}</annotation>

</semantics>

</math><img src="./9c454bb35f050556d361ee85e06ca923b16a3bf4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.575ex; height:2.676ex;" alt="{\displaystyle i^{th}}" loading="lazy"> bit of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> randomly generates a set of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> queries <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{1},\ldots q_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{1},\ldots q_{k}}</annotation>

</semantics>

</math><img src="./8fd101367a6583c63b7e18fb715ec0c9995fb49e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.361ex; height:2.009ex;" alt="{\displaystyle q_{1},\ldots q_{k}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> can be computed from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(x)_{q_{1}},\ldots C(x)_{q_{k}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C(x)_{q_{1}},\ldots C(x)_{q_{k}}}</annotation>

</semantics>

</math><img src="./0e0016ec1b2e2d9f4a9f6d9a47af5426be0c98be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.577ex; height:3.009ex;" alt="{\displaystyle C(x)_{q_{1}},\ldots C(x)_{q_{k}}}" loading="lazy"> using the local decoding algorithm <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">. The user sends each query to a different server, and each server responds with the bit requested. The user then uses <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> to compute <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> from the responses.<a href="#cite_note-LDC1-8">[8]</a><a href="#cite_note-PIR-11">[11]</a>

Because the decoding algorithm is perfectly smooth, each query <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{j}}</annotation>

</semantics>

</math><img src="./e0d567ac2d170501680d2efa4c1d71d6a8569ef1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.947ex; height:2.343ex;" alt="{\displaystyle q_{j}}" loading="lazy"> is uniformly distributed over the codeword; thus, no individual server can gain any information about the user's intentions, so the protocol is private as long as the servers do not communicate.<a href="#cite_note-PIR-11">[11]</a>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="The_Hadamard_code">The Hadamard code</h3></div>

The <a href="Hadamard" class="mw-redirect" title="Hadamard">Hadamard</a> (or Walsh-Hadamard) code is an example of a simple locally decodable code that maps a string of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> to a codeword of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k}}</annotation>

</semantics>

</math><img src="./2d82641ae2702b0db07dd11830af27b9ee0cd196.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.251ex; height:2.676ex;" alt="{\displaystyle 2^{k}}" loading="lazy">. The codeword for a string <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./4535992aa6b5e1b799665d67ffd780cecc03b300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.943ex; height:3.176ex;" alt="{\displaystyle x\in \{0,1\}^{k}}" loading="lazy"> is constructed as follows: for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{j}\in \{0,1\}^{k}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{j}\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./29b59347193cb1cbd531f6b8ac7eced512894244.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.753ex; height:3.343ex;" alt="{\displaystyle a_{j}\in \{0,1\}^{k}}" loading="lazy">, the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j^{th}}</annotation>

</semantics>

</math><img src="./04bfd24f79d376ca8156511feb951588f358a928.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:2.758ex; height:3.009ex;" alt="{\displaystyle j^{th}}" loading="lazy"> bit of the codeword is equal to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\odot a_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\odot a_{j}}</annotation>

</semantics>

</math><img src="./82795f3c6074ac27be9489e7567da46b6eb93002.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.31ex; height:2.676ex;" alt="{\displaystyle x\odot a_{j}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\odot y=\sum \limits _{i=1}^{k}x_{i}y_{i}}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\odot y=\sum \limits _{i=1}^{k}x_{i}y_{i}}</annotation>

</semantics>

</math><img src="./e29b92256dfd147328f0ac0e6c0053659e6722b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:16.234ex; height:7.343ex;" alt="{\displaystyle x\odot y=\sum \limits _{i=1}^{k}x_{i}y_{i}}" loading="lazy"> (mod 2). It is easy to see that every codeword has a <a href="Hamming_distance" title="Hamming distance">Hamming distance</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {n}{2}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {n}{2}}}</annotation>

</semantics>

</math><img src="./1216d48de276dc45542cb80b1e49037131ec9624.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:2.231ex; height:4.676ex;" alt="{\displaystyle {\frac {n}{2}}}" loading="lazy"> from every other codeword.

The local decoding algorithm has query complexity 2, and the entire original message can be decoded with good probability if the codeword is corrupted in less than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{4}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{4}}}</annotation>

</semantics>

</math><img src="./a2dfb63ee75ec084f2abb25d248bc151a2687508.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:1.999ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{4}}}" loading="lazy"> of its bits. For <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho <{\frac {1}{4}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho <{\frac {1}{4}}}</annotation>

</semantics>

</math><img src="./634d2f34dc6bec6ebe87f78b8ed68aef4aea7421.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.299ex; height:5.176ex;" alt="{\displaystyle \rho <{\frac {1}{4}}}" loading="lazy">, if the codeword is corrupted in a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho }</annotation>

</semantics>

</math><img src="./1f7d439671d1289b6a816e6af7a304be40608d64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.202ex; height:2.176ex;" alt="{\displaystyle \rho }" loading="lazy"> fraction of places, a local decoding algorithm can recover the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i^{th}}</annotation>

</semantics>

</math><img src="./9c454bb35f050556d361ee85e06ca923b16a3bf4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.575ex; height:2.676ex;" alt="{\displaystyle i^{th}}" loading="lazy"> bit of the original message with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-2\rho }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-2\rho }</annotation>

</semantics>

</math><img src="./f47d17a81776a0ef442179c345f31eef0e88e0a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.367ex; height:2.676ex;" alt="{\displaystyle 1-2\rho }" loading="lazy">.

Proof: Given a codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> and an index <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">, the algorithm to recover the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i^{th}}</annotation>

</semantics>

</math><img src="./9c454bb35f050556d361ee85e06ca923b16a3bf4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.575ex; height:2.676ex;" alt="{\displaystyle i^{th}}" loading="lazy"> bit of the original message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> works as follows:

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e^{j}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e^{j}}</annotation>

</semantics>

</math><img src="./8f1bcef4362c1f4fca4b0d494b2cf190ce73ad09.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.993ex; height:2.676ex;" alt="{\displaystyle e^{j}}" loading="lazy"> refer to the vector in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./336678931c6d9bfdbbc2062a2e523aa9c1c3a6ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.772ex; height:3.176ex;" alt="{\displaystyle \{0,1\}^{k}}" loading="lazy"> that has 1 in the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j^{th}}</annotation>

</semantics>

</math><img src="./04bfd24f79d376ca8156511feb951588f358a928.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:2.758ex; height:3.009ex;" alt="{\displaystyle j^{th}}" loading="lazy"> position and 0s elsewhere. For <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./ba8d9424bd0a3b9fab8338ffafe74faf7ec339bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.769ex; height:3.176ex;" alt="{\displaystyle y\in \{0,1\}^{k}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(y)}</annotation>

</semantics>

</math><img src="./aaa9215c6afa4892692ba05ae4c44f23600ea79d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.243ex; height:2.843ex;" alt="{\displaystyle f(y)}" loading="lazy"> denotes the single bit in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> that corresponds to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\odot y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\odot y}</annotation>

</semantics>

</math><img src="./152680622115d905323a60065e7e60c54ac70831.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.326ex; height:2.343ex;" alt="{\displaystyle x\odot y}" loading="lazy">. The algorithm chooses a random vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./ba8d9424bd0a3b9fab8338ffafe74faf7ec339bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.769ex; height:3.176ex;" alt="{\displaystyle y\in \{0,1\}^{k}}" loading="lazy"> and the vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y'=y\oplus e^{i}}">

<msup>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y'=y\oplus e^{i}}</annotation>

</semantics>

</math><img src="./495a60d140c3cad2d33256cd252e91ff6a71a2c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.823ex; height:3.009ex;" alt="{\displaystyle y'=y\oplus e^{i}}" loading="lazy"> (where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \oplus }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \oplus }</annotation>

</semantics>

</math><img src="./8b16e2bdaefee9eed86d866e6eba3ac47c710f60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \oplus }" loading="lazy"> denotes <a href="Bitwise_XOR" class="mw-redirect" title="Bitwise XOR">bitwise XOR</a>). The algorithm outputs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(y)\oplus f(y')}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(y)\oplus f(y')}</annotation>

</semantics>

</math><img src="./0d5d7b083b689181584b3edbc686a0613a379150.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.017ex; height:3.009ex;" alt="{\displaystyle f(y)\oplus f(y')}" loading="lazy"> (mod 2).

Correctness: By linearity,

<msup>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x\odot y)\oplus (x\odot y')=(x\odot y)\oplus (x\odot (y\oplus e^{i}))=(x\odot y)\oplus (x\odot y)\oplus (x\odot e^{i})=x\odot e^{i}}</annotation>

</semantics>

</math><img src="./1efce844bf7af29313df2a57bb342bc20a441810.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:84.605ex; height:3.176ex;" alt="{\displaystyle (x\odot y)\oplus (x\odot y')=(x\odot y)\oplus (x\odot (y\oplus e^{i}))=(x\odot y)\oplus (x\odot y)\oplus (x\odot e^{i})=x\odot e^{i}}" loading="lazy">

But <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x\odot e^{i})=x_{i}}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x\odot e^{i})=x_{i}}</annotation>

</semantics>

</math><img src="./9fd733394656cd9af50b674b2a61092ffaa7c5fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.09ex; height:3.176ex;" alt="{\displaystyle (x\odot e^{i})=x_{i}}" loading="lazy">, so we just need to show that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(y)=x\odot y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(y)=x\odot y}</annotation>

</semantics>

</math><img src="./0a8e7f718e03a8436c710eda027be55e98360721.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.667ex; height:2.843ex;" alt="{\displaystyle f(y)=x\odot y}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(y')=x\odot y'}">

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(y')=x\odot y'}</annotation>

</semantics>

</math><img src="./d8683b0be794fdd453d39db24298e06705e2029f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.047ex; height:3.009ex;" alt="{\displaystyle f(y')=x\odot y'}" loading="lazy"> with good probability.

Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y'}</annotation>

</semantics>

</math><img src="./3a535de94a2183d7130731eab8a83531d7c35c6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.845ex; height:2.843ex;" alt="{\displaystyle y'}" loading="lazy"> are uniformly distributed (even though they are dependent), the <a href="Union_bound" class="mw-redirect" title="Union bound">union bound</a> implies that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(y)=x\odot y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(y)=x\odot y}</annotation>

</semantics>

</math><img src="./0a8e7f718e03a8436c710eda027be55e98360721.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.667ex; height:2.843ex;" alt="{\displaystyle f(y)=x\odot y}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(y')=x\odot y'}">

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(y')=x\odot y'}</annotation>

</semantics>

</math><img src="./d8683b0be794fdd453d39db24298e06705e2029f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.047ex; height:3.009ex;" alt="{\displaystyle f(y')=x\odot y'}" loading="lazy"> with probability at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-2\rho }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-2\rho }</annotation>

</semantics>

</math><img src="./f47d17a81776a0ef442179c345f31eef0e88e0a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.367ex; height:2.676ex;" alt="{\displaystyle 1-2\rho }" loading="lazy">. Note: to amplify the probability of success, one can repeat the procedure with different random vectors and take the majority answer.

<div class="mw-heading mw-heading3"><h3 id="The_Reed–Muller_code">The Reed–Muller code</h3></div>

The main idea behind local decoding of <a href="Reed-Muller_codes" class="mw-redirect" title="Reed-Muller codes">Reed-Muller codes</a> is <a href="Polynomial_interpolation" title="Polynomial interpolation">polynomial interpolation</a>. The key concept behind a Reed-Muller code is a multivariate polynomial of degree <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"> variables. The message is treated as the evaluation of a polynomial at a set of predefined points. To encode these values, a polynomial is extrapolated from them, and the codeword is the evaluation of that polynomial on all possible points. At a high level, to decode a point of this polynomial, the decoding algorithm chooses a set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> of points on a line that passes through the point of interest <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">. It then queries the codeword for the evaluation of the polynomial on points in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> and interpolates that polynomial. Then it is simple to evaluate the polynomial at the point that will yield <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">. This roundabout way of evaluating <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is useful because (a) the algorithm can be repeated using different lines through the same point to improve the probability of correctness, and (b) the queries are uniformly distributed over the codeword.

More formally, let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} }</annotation>

</semantics>

</math><img src="./573f72afae7df709959ab1a58cd643743466a187.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.42ex; height:2.176ex;" alt="{\displaystyle \mathbb {F} }" loading="lazy"> be a <a href="Finite_field" title="Finite field">finite field</a>, and let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l,d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l,d}</annotation>

</semantics>

</math><img src="./ec717a943df716fe7c046fb02044276c1d373525.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.943ex; height:2.509ex;" alt="{\displaystyle l,d}" loading="lazy"> be numbers with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d<|\mathbb {F} |}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d<|\mathbb {F} |}</annotation>

</semantics>

</math><img src="./e7694358cd2bd7132a22e50dd69057a11d20b487.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.028ex; height:2.843ex;" alt="{\displaystyle d<|\mathbb {F} |}" loading="lazy">. The Reed-Muller code with parameters <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} ,l,d}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} ,l,d}</annotation>

</semantics>

</math><img src="./dacb25ed4b763e51527023f50e5c412a5f95d6ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.397ex; height:2.509ex;" alt="{\displaystyle \mathbb {F} ,l,d}" loading="lazy"> is the function RM : <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} ^{\binom {l+d}{d}}\rightarrow \mathbb {F} ^{|\mathbb {F} |^{l}}}">

<msup>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} ^{\binom {l+d}{d}}\rightarrow \mathbb {F} ^{|\mathbb {F} |^{l}}}</annotation>

</semantics>

</math><img src="./c80378c897ff2a3dbe73709914ac5776b552892f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.497ex; height:3.843ex;" alt="{\displaystyle \mathbb {F} ^{\binom {l+d}{d}}\rightarrow \mathbb {F} ^{|\mathbb {F} |^{l}}}" loading="lazy"> that maps every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy">-variable polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> over <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} }</annotation>

</semantics>

</math><img src="./573f72afae7df709959ab1a58cd643743466a187.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.42ex; height:2.176ex;" alt="{\displaystyle \mathbb {F} }" loading="lazy"> of total degree <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> to the values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> on all the inputs in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} ^{l}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} ^{l}}</annotation>

</semantics>

</math><img src="./d0dc4a9b057e8f3ecd2278bcf89093350c15a45f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.143ex; height:2.676ex;" alt="{\displaystyle \mathbb {F} ^{l}}" loading="lazy">. That is, the input is a polynomial of the form

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x_{1},\ldots ,x_{l})=\sum \limits _{i_{1}+\ldots +i_{l}\leq d}c_{i_{1},\ldots ,i_{l}}x_{1}^{i_{1}}x_{2}^{i_{2}}\cdots x_{l}^{i_{l}}}</annotation>

</semantics>

</math><img src="./e9cb4ca80d4d800f2bb08d9f404cc2a25adb6583.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:44.523ex; height:6.009ex;" alt="{\displaystyle P(x_{1},\ldots ,x_{l})=\sum \limits _{i_{1}+\ldots +i_{l}\leq d}c_{i_{1},\ldots ,i_{l}}x_{1}^{i_{1}}x_{2}^{i_{2}}\cdots x_{l}^{i_{l}}}" loading="lazy">

specified by the interpolation of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {l+d}{d}}}">

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\binom {l+d}{d}}}</annotation>

</semantics>

</math><img src="./926c4709c17d2499c888af8dbc0a766d4219da25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:8.171ex; height:6.176ex;" alt="{\displaystyle {\binom {l+d}{d}}}" loading="lazy"> values of the predefined points and the output is the sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{P(x_{1},\ldots ,x_{l})\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{P(x_{1},\ldots ,x_{l})\}}</annotation>

</semantics>

</math><img src="./eda8831fefa5a77492428a2465e0503f31c8ed5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.494ex; height:2.843ex;" alt="{\displaystyle \{P(x_{1},\ldots ,x_{l})\}}" loading="lazy"> for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1},\ldots ,x_{l}\in \mathbb {F} }">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1},\ldots ,x_{l}\in \mathbb {F} }</annotation>

</semantics>

</math><img src="./b505653e05102c2af7809b65c43ac3e828ae7534.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.875ex; height:2.509ex;" alt="{\displaystyle x_{1},\ldots ,x_{l}\in \mathbb {F} }" loading="lazy">.<a href="#cite_note-AB1942-14">[14]</a>

To recover the value of a degree <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> polynomial at a point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\in \mathbb {F} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\in \mathbb {F} ^{n}}</annotation>

</semantics>

</math><img src="./a4b5b7b39631fad451ca0b5b27a18724cd6a0956.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.144ex; height:2.343ex;" alt="{\displaystyle w\in \mathbb {F} ^{n}}" loading="lazy">, the local decoder shoots a random <a href="Affine_geometry" title="Affine geometry">affine</a> line through <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy">. Then it picks <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d+1}</annotation>

</semantics>

</math><img src="./056e0c06c828dbe71a0f9021b2828ff176a3d337.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d+1}" loading="lazy"> points on that line, which it uses to interpolate the polynomial and then evaluate it at the point where the result is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy">. To do so, the algorithm picks a vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in \mathbb {F} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in \mathbb {F} ^{n}}</annotation>

</semantics>

</math><img src="./80b733db862fd41b12c3e29064ad5dfcbdb797da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.607ex; height:2.343ex;" alt="{\displaystyle v\in \mathbb {F} ^{n}}" loading="lazy"> uniformly at random and considers the line <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L=\{w+\lambda v\mid \lambda \in \mathbb {F} \}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L=\{w+\lambda v\mid \lambda \in \mathbb {F} \}}</annotation>

</semantics>

</math><img src="./47399688f7c1a57f82ad091917c2faf4ae5be3ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.547ex; height:2.843ex;" alt="{\displaystyle L=\{w+\lambda v\mid \lambda \in \mathbb {F} \}}" loading="lazy"> through <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy">. The algorithm picks an arbitrary subset <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} }</annotation>

</semantics>

</math><img src="./573f72afae7df709959ab1a58cd643743466a187.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.42ex; height:2.176ex;" alt="{\displaystyle \mathbb {F} }" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |S|=d+1}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |S|=d+1}</annotation>

</semantics>

</math><img src="./2bd5df0d45a73d380459a7d2b3da3c73a7b83f4e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.11ex; height:2.843ex;" alt="{\displaystyle |S|=d+1}" loading="lazy">, and queries coordinates of the codeword that correspond to points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w+\lambda v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w+\lambda v}</annotation>

</semantics>

</math><img src="./025bff7ccb825d907918487bb33df46716f1db5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.987ex; height:2.343ex;" alt="{\displaystyle w+\lambda v}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda \in S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda \in S}</annotation>

</semantics>

</math><img src="./2ff7eb035f9014e9df07d27122864c123b67363a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.695ex; height:2.176ex;" alt="{\displaystyle \lambda \in S}" loading="lazy"> and obtains values <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{e_{\lambda }\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{e_{\lambda }\}}</annotation>

</semantics>

</math><img src="./0279d4833bde259d605f99bbe79d2d1b443fb58d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.599ex; height:2.843ex;" alt="{\displaystyle \{e_{\lambda }\}}" loading="lazy">. Then it uses polynomial interpolation to recover the unique univariate polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> with degree less than or equal to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(\lambda )=e_{\lambda }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(\lambda )=e_{\lambda }}</annotation>

</semantics>

</math><img src="./5829c40a7f1650c8a5b1f202f471da2fbf661faf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.876ex; height:2.843ex;" alt="{\displaystyle h(\lambda )=e_{\lambda }}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda \in S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda \in S}</annotation>

</semantics>

</math><img src="./2ff7eb035f9014e9df07d27122864c123b67363a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.695ex; height:2.176ex;" alt="{\displaystyle \lambda \in S}" loading="lazy">. Then, to get the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy">, it just evaluates <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(0)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(0)}</annotation>

</semantics>

</math><img src="./8bbd2e4a81a9d3a769730d619aa10a0a766db75c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.311ex; height:2.843ex;" alt="{\displaystyle h(0)}" loading="lazy">. To recover a single value of the original message, one chooses <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> to be one of the points that defines the polynomial.<a href="#cite_note-LDC1-8">[8]</a><a href="#cite_note-AB1942-14">[14]</a>

Each individual query is distributed uniformly at random over the codeword. Thus, if the codeword is corrupted in at most a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>

</semantics>

</math><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy"> fraction of locations, by the union bound, the probability that the algorithm samples only uncorrupted coordinates (and thus correctly recovers the bit) is at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-(d+1)\delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-(d+1)\delta }</annotation>

</semantics>

</math><img src="./15256895076dbfaa215547a3af77bc7e571ce625.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.08ex; height:2.843ex;" alt="{\displaystyle 1-(d+1)\delta }" loading="lazy">.<a href="#cite_note-LDC1-8">[8]</a>

For other decoding algorithms, see.<a href="#cite_note-LDC1-8">[8]</a>

<ul><li><a href="Private_information_retrieval" title="Private information retrieval">Private information retrieval</a></li>

<li><a href="Linear_cryptanalysis" title="Linear cryptanalysis">Linear cryptanalysis</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFSergey_Yekhanin" class="citation web cs1">Sergey Yekhanin. <a rel="nofollow" class="external text" href="http://research.microsoft.com/en-us/um/people/yekhanin/papers/survey_iwcc.pdf">"Locally decodable codes: a brief survey"</a> (PDF).</cite>

</li>

<li id="cite_note-PrivateLDC-2"><a href="#cite_ref-PrivateLDC_2-0">^</a> <cite id="CITEREFRafail_OstrovskyOmkant_PandeyAmit_Sahai" class="citation web cs1">Rafail Ostrovsky; Omkant Pandey; Amit Sahai. <a rel="nofollow" class="external text" href="http://eprint.iacr.org/2007/025.pdf">"Private Locally Decodable Codes"</a> (PDF).</cite>

</li>

<li id="cite_note-newLDCPIR-3">^ <a href="#cite_ref-newLDCPIR_3-0">a</a> <a href="#cite_ref-newLDCPIR_3-1">b</a> Sergey Yekhanin. New locally decodable codes and private information retrieval schemes, <a rel="nofollow" class="external text" href="http://www.eccc.hpi-web.de/eccc-reports/2006/TR06-127/index.html">Technical Report ECCC TR06-127</a>, 2006.

</li>

<li id="cite_note-LTCvsLDC-4"><a href="#cite_ref-LTCvsLDC_4-0">^</a> <cite id="CITEREFKaufmanViderman" class="citation web cs1"><a href="Tali_Kaufman" title="Tali Kaufman">Kaufman, Tali</a>; Viderman, Michael. <a rel="nofollow" class="external text" href="http://eccc.hpi-web.de/report/2010/130/revision/1/download/">"Locally Testable vs. Locally Decodable Codes"</a>.</cite>

</li>

<li id="cite_note-AppCodingTheory-5">^ <a href="#cite_ref-AppCodingTheory_5-0">a</a> <a href="#cite_ref-AppCodingTheory_5-1">b</a> <a href="#cite_ref-AppCodingTheory_5-2">c</a> <cite id="CITEREFLuca_Trevisan" class="citation web cs1">Luca Trevisan. <a rel="nofollow" class="external text" href="http://theory.stanford.edu/~trevisan/pubs/codingsurvey.pdf">"Some Applications of Coding Theory in Computational Complexity"</a> (PDF).</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFAroraBarak2009" class="citation book cs1"><a href="Sanjeev_Arora" title="Sanjeev Arora">Arora, Sanjeev</a>; Barak, Boaz (2009). "Section 19.5". <a rel="nofollow" class="external text" href="http://www.cs.princeton.edu/theory/complexity/">Computational Complexity: A Modern Approach</a>. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-42426-4</bdi>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <a href="#CITEREFAroraBarak2009">Arora & Barak 2009</a>, Section 19.4.3

</li>

<li id="cite_note-LDC1-8">^ <a href="#cite_ref-LDC1_8-0">a</a> <a href="#cite_ref-LDC1_8-1">b</a> <a href="#cite_ref-LDC1_8-2">c</a> <a href="#cite_ref-LDC1_8-3">d</a> <a href="#cite_ref-LDC1_8-4">e</a> <a href="#cite_ref-LDC1_8-5">f</a> <a href="#cite_ref-LDC1_8-6">g</a> <a href="#cite_ref-LDC1_8-7">h</a> <a href="#cite_ref-LDC1_8-8">i</a> <cite id="CITEREFSergey_Yekhanin" class="citation web cs1">Sergey Yekhanin. <a rel="nofollow" class="external text" href="http://research.microsoft.com/en-us/um/people/yekhanin/Papers/LDC_now.pdf">"Locally Decodable Codes"</a> (PDF).</cite>

</li>

<li id="cite_note-LDC2-9">^ <a href="#cite_ref-LDC2_9-0">a</a> <a href="#cite_ref-LDC2_9-1">b</a> <cite id="CITEREFSergey_Yekhanin" class="citation web cs1">Sergey Yekhanin. <a rel="nofollow" class="external text" href="https://www.iacr.org/workshops/tcc2012/survey_tcc.pdf">"Locally Decodable Codes"</a> (PDF).</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www-math.ucdenver.edu/~wcherowi/courses/m7409/mariner9talk.pdf">"Combinatorics in Space The Mariner 9 Telemetry System"</a> (PDF).</cite>

</li>

<li id="cite_note-PIR-11">^ <a href="#cite_ref-PIR_11-0">a</a> <a href="#cite_ref-PIR_11-1">b</a> <a href="#cite_ref-PIR_11-2">c</a> <a href="#cite_ref-PIR_11-3">d</a> <cite id="CITEREFSergey_Yekhanin" class="citation web cs1">Sergey Yekhanin. <a rel="nofollow" class="external text" href="http://research.microsoft.com/pubs/141305/cacm_2010.pdf">"Private Information retrieval"</a> (PDF).</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <a href="#CITEREFAroraBarak2009">Arora & Barak 2009</a>, Section 19.4

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <a href="#CITEREFAroraBarak2009">Arora & Barak 2009</a>, Section 11.5.2

</li>

<li id="cite_note-AB1942-14">^ <a href="#cite_ref-AB1942_14-0">a</a> <a href="#cite_ref-AB1942_14-1">b</a> <a href="#CITEREFAroraBarak2009">Arora & Barak 2009</a>, Section 19.4.2

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-24" href="https://en.wikipedia.org/wiki/?title=Locally_decodable_code&oldid=1302288920">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>